



<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      <meta http-equiv="x-ua-compatible" content="ie=edge">
      
        <meta name="description" content="Hrbust_ACM's Wiki">
      
      
        <link rel="canonical" href="https://hrbust-acm.online/S/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2/">
      
      
        <meta name="author" content="Hrbust_Acmer">
      
      
        <meta name="lang:clipboard.copy" content="复制">
      
        <meta name="lang:clipboard.copied" content="已复制">
      
        <meta name="lang:search.language" content="ja">
      
        <meta name="lang:search.pipeline.stopwords" content="True">
      
        <meta name="lang:search.pipeline.trimmer" content="True">
      
        <meta name="lang:search.result.none" content="没有找到符合条件的结果">
      
        <meta name="lang:search.result.one" content="找到 1 个符合条件的结果">
      
        <meta name="lang:search.result.other" content="# 个符合条件的结果">
      
        <meta name="lang:search.tokenizer" content="[\uff0c\u3002]+">
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-4.6.3">
    
    
      
        <title>启发式搜索 - Hrbust_ACM's Wiki</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/application.adb8469c.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/application-palette.a8b3c06d.css">
      
      
        
        
        <meta name="theme-color" content="#ef5350">
      
    
    
      <script src="../../assets/javascripts/modernizr.86422ebf.js"></script>
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto","Helvetica Neue",Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono","Courier New",Courier,monospace}</style>
      
    
    <link rel="stylesheet" href="../../assets/fonts/material-icons.css">
    
    
    
      
    
    
  </head>
  
    
    
    <body dir="ltr" data-md-color-primary="red" data-md-color-accent="blue">
  
    <svg class="md-svg">
      <defs>
        
        
          <svg xmlns="http://www.w3.org/2000/svg" width="416" height="448" viewBox="0 0 416 448" id="__github"><path fill="currentColor" d="M160 304q0 10-3.125 20.5t-10.75 19T128 352t-18.125-8.5-10.75-19T96 304t3.125-20.5 10.75-19T128 256t18.125 8.5 10.75 19T160 304zm160 0q0 10-3.125 20.5t-10.75 19T288 352t-18.125-8.5-10.75-19T256 304t3.125-20.5 10.75-19T288 256t18.125 8.5 10.75 19T320 304zm40 0q0-30-17.25-51T296 232q-10.25 0-48.75 5.25Q229.5 240 208 240t-39.25-2.75Q130.75 232 120 232q-29.5 0-46.75 21T56 304q0 22 8 38.375t20.25 25.75 30.5 15 35 7.375 37.25 1.75h42q20.5 0 37.25-1.75t35-7.375 30.5-15 20.25-25.75T360 304zm56-44q0 51.75-15.25 82.75-9.5 19.25-26.375 33.25t-35.25 21.5-42.5 11.875-42.875 5.5T212 416q-19.5 0-35.5-.75t-36.875-3.125-38.125-7.5-34.25-12.875T37 371.5t-21.5-28.75Q0 312 0 260q0-59.25 34-99-6.75-20.5-6.75-42.5 0-29 12.75-54.5 27 0 47.5 9.875t47.25 30.875Q171.5 96 212 96q37 0 70 8 26.25-20.5 46.75-30.25T376 64q12.75 25.5 12.75 54.5 0 21.75-6.75 42 34 40 34 99.5z"/></svg>
        
      </defs>
    </svg>
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" data-md-component="overlay" for="__drawer"></label>
    
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid">
    <div class="md-flex">
      <div class="md-flex__cell md-flex__cell--shrink">
        <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" aria-label="Hrbust_ACM's Wiki" class="md-header-nav__button md-logo">
          
            <i class="md-icon"></i>
          
        </a>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        <label class="md-icon md-icon--menu md-header-nav__button" for="__drawer"></label>
      </div>
      <div class="md-flex__cell md-flex__cell--stretch">
        <div class="md-flex__ellipsis md-header-nav__title" data-md-component="title">
          
            <span class="md-header-nav__topic">
              Hrbust_ACM's Wiki
            </span>
            <span class="md-header-nav__topic">
              
                启发式搜索
              
            </span>
          
        </div>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        
          <label class="md-icon md-icon--search md-header-nav__button" for="__search"></label>
          
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" aria-label="search" name="query" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="query" data-md-state="active">
      <label class="md-icon md-search__icon" for="__search"></label>
      <button type="reset" class="md-icon md-search__icon" data-md-component="reset" tabindex="-1">
        &#xE5CD;
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="result">
          <div class="md-search-result__meta">
            键入以开始搜索
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
        
      </div>
      
        <div class="md-flex__cell md-flex__cell--shrink">
          <div class="md-header-nav__source">
            


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
          </div>
        </div>
      
    </div>
  </nav>
</header>
    
    <div class="md-container">
      
        
      
      
        

  

<nav class="md-tabs md-tabs--active" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../.." class="md-tabs__link">
          首页
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../DFS/" class="md-tabs__link md-tabs__link--active">
          搜索
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" class="md-tabs__link">
          动态规划
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" class="md-tabs__link">
          数据结构
        </a>
      
    </li>
  

      
        
  
  
    
    
  
  
    <li class="md-tabs__item">
      
        <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" class="md-tabs__link">
          图论
        </a>
      
    </li>
  

  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" class="md-tabs__link">
          字符串
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" class="md-tabs__link">
          计算几何
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Others/Time/" class="md-tabs__link">
          附录
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
      
      <main class="md-main" role="main">
        <div class="md-main__inner md-grid" data-md-component="container">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" data-md-level="0">
  <label class="md-nav__title md-nav__title--site" for="__drawer">
    <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" class="md-nav__button md-logo">
      
        <i class="md-icon"></i>
      
    </a>
    Hrbust_ACM's Wiki
  </label>
  
    <div class="md-nav__source">
      


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-1" type="checkbox" id="nav-1">
    
    <label class="md-nav__link" for="nav-1">
      首页
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-1">
        首页
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../.." title="Getting Started" class="md-nav__link">
      Getting Started
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../home/" title="Wiki介绍" class="md-nav__link">
      Wiki介绍
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../faq/" title="如何使用" class="md-nav__link">
      如何使用
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-2" type="checkbox" id="nav-2" checked>
    
    <label class="md-nav__link" for="nav-2">
      搜索
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-2">
        搜索
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../DFS/" title="深度优先搜索" class="md-nav__link">
      深度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../BFS/" title="广度优先搜索" class="md-nav__link">
      广度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../DeSearch/" title="双向搜索" class="md-nav__link">
      双向搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../Memory_Search/" title="记忆化搜索" class="md-nav__link">
      记忆化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alpha-beta%E5%89%AA%E6%9E%9D/" title="极大极小化搜索" class="md-nav__link">
      极大极小化搜索
    </a>
  </li>

        
          
          
          

  


  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-toggle md-nav__toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
    
    <a href="./" title="启发式搜索" class="md-nav__link md-nav__link--active">
      启发式搜索
    </a>
    
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-3" type="checkbox" id="nav-3">
    
    <label class="md-nav__link" for="nav-3">
      动态规划
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-3">
        动态规划
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" title="状态压缩DP" class="md-nav__link">
      状态压缩DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A0%91%E5%BD%A2DP/" title="树形 DP" class="md-nav__link">
      树形 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E5%8C%BA%E9%97%B4DP/" title="区间 DP" class="md-nav__link">
      区间 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%95%B0%E4%BD%8DDP/" title="数位 DP" class="md-nav__link">
      数位 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A6%82%E7%8E%87DP/" title="概率 DP" class="md-nav__link">
      概率 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%9C%9F%E6%9C%9BDP/" title="期望 DP" class="md-nav__link">
      期望 DP
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4" type="checkbox" id="nav-4">
    
    <label class="md-nav__link" for="nav-4">
      数据结构
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-4">
        数据结构
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" title="一维树状数组" class="md-nav__link">
      一维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%842/" title="二维树状数组" class="md-nav__link">
      二维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/ST/" title="ST表" class="md-nav__link">
      ST表
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/RMQ/" title="RMQ" class="md-nav__link">
      RMQ
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-5" type="checkbox" id="nav-4-5">
    
    <label class="md-nav__link" for="nav-4-5">
      线段树
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-5">
        线段树
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91lazy/" title="线段树lazy标记" class="md-nav__link">
      线段树lazy标记
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6/" title="线段树区间合并" class="md-nav__link">
      线段树区间合并
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%89%AB%E6%8F%8F%E7%BA%BF/" title="扫描线" class="md-nav__link">
      扫描线
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-6" type="checkbox" id="nav-4-6">
    
    <label class="md-nav__link" for="nav-4-6">
      树链剖分
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-6">
        树链剖分
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%A8/" title="点剖" class="md-nav__link">
      点剖
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%BE%B9%E5%89%96/" title="边剖" class="md-nav__link">
      边剖
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E5%88%86%E5%9D%97/" title="分块算法" class="md-nav__link">
      分块算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%8E%AB%E9%98%9F/" title="莫队算法" class="md-nav__link">
      莫队算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%86%E6%B2%BB/" title="点分治" class="md-nav__link">
      点分治
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5">
    
    <label class="md-nav__link" for="nav-5">
      图论
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        图论
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-1" type="checkbox" id="nav-5-1">
    
    <label class="md-nav__link" for="nav-5-1">
      二分图
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-1">
        二分图
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" title="匈牙利算法" class="md-nav__link">
      匈牙利算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/KM%E7%AE%97%E6%B3%95/" title="KM 算法" class="md-nav__link">
      KM 算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-2" type="checkbox" id="nav-5-2">
    
    <label class="md-nav__link" for="nav-5-2">
      网络流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-2">
        网络流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/EK/" title="EK 算法" class="md-nav__link">
      EK 算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/Dinic/" title="Dinic+当前弧优化" class="md-nav__link">
      Dinic+当前弧优化
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/ISAP/" title="ISAP算法" class="md-nav__link">
      ISAP算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-3" type="checkbox" id="nav-5-3">
    
    <label class="md-nav__link" for="nav-5-3">
      费用流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-3">
        费用流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/SPFA%E8%B4%B9%E7%94%A8%E6%B5%81/" title="SPFA 费用流" class="md-nav__link">
      SPFA 费用流
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      字符串
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        字符串
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" title="字典树" class="md-nav__link">
      字典树
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="AC自动机" class="md-nav__link">
      AC自动机
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7">
    
    <label class="md-nav__link" for="nav-7">
      计算几何
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        计算几何
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" title="点积叉积的运用" class="md-nav__link">
      点积叉积的运用
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%87%B8%E5%8C%85%E7%9A%84%E6%B1%82%E5%8F%96/" title="凸包的求取" class="md-nav__link">
      凸包的求取
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4/" title="半平面交" class="md-nav__link">
      半平面交
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E6%97%8B%E8%BD%AC%E5%8D%A1%E5%A3%B3/" title="旋转卡壳" class="md-nav__link">
      旋转卡壳
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      附录
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        附录
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/Time/" title="时间/空间复杂度" class="md-nav__link">
      时间/空间复杂度
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/exem/" title="习题" class="md-nav__link">
      习题
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                  <a href="https://github.com/acm-hrbust-wiki/wiki/tree/docs/S/启发式搜索.md" title="编辑此页" class="md-icon md-content__icon">&#xE3C9;</a>
                
                
                  <h1>启发式搜索</h1>
                
                <table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="c1">//poj 1077 A* 解决八数码问题（3*3 的棋盘，有 8 个标号是 1-8 的棋子，一个空格。每</span>
<span class="mi">7</span> <span class="err">次可以把一个与空格相邻的棋子移动到空格上，给出一个目标棋盘，问最少移动次数）</span>
<span class="cp">#include</span> <span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;cstdlib&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;string&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;queue&gt;</span><span class="cp"></span>
    <span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">maxn</span> <span class="o">=</span> <span class="mi">15</span><span class="p">,</span> <span class="n">maxs</span> <span class="o">=</span> <span class="mi">362885</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">AStar</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="k">const</span> <span class="kt">int</span> <span class="n">nxt</span><span class="p">[</span><span class="mi">4</span><span class="p">][</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="p">{{</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">},</span> <span class="p">{</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">},</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">},</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">}};</span>
    <span class="k">const</span> <span class="kt">char</span> <span class="n">dir</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="sc">&#39;u&#39;</span><span class="p">,</span> <span class="sc">&#39;d&#39;</span><span class="p">,</span> <span class="sc">&#39;l&#39;</span><span class="p">,</span> <span class="sc">&#39;r&#39;</span><span class="p">};</span>
    <span class="kt">int</span> <span class="n">bit</span><span class="p">[</span><span class="n">maxn</span><span class="p">],</span> <span class="n">fact</span><span class="p">[</span><span class="n">maxn</span><span class="p">];</span>
    <span class="n">AStar</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">fact</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
            <span class="n">fact</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">fact</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">i</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kr">inline</span> <span class="kt">int</span> <span class="n">ask</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="p">)</span>
            <span class="n">ret</span> <span class="o">+=</span> <span class="n">bit</span><span class="p">[</span><span class="n">x</span><span class="p">],</span> <span class="n">x</span> <span class="o">-=</span> <span class="n">x</span> <span class="o">&amp;</span> <span class="o">-</span><span class="n">x</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">ret</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kr">inline</span> <span class="kt">void</span> <span class="n">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">x</span> <span class="o">&lt;=</span> <span class="mi">9</span><span class="p">)</span>
            <span class="n">bit</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">+=</span> <span class="n">d</span><span class="p">,</span> <span class="n">x</span> <span class="o">+=</span> <span class="n">x</span> <span class="o">&amp;</span> <span class="o">-</span><span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">struct</span> <span class="n">Node</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span>
        <span class="n">string</span> <span class="n">s</span><span class="p">,</span> <span class="n">ans</span><span class="p">;</span>
        <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span><span class="p">(</span><span class="k">const</span> <span class="n">Node</span> <span class="o">&amp;</span><span class="n">rhs</span><span class="p">)</span> <span class="k">const</span>
        <span class="p">{</span>
            <span class="k">return</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="n">rhs</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">rhs</span><span class="p">.</span><span class="n">y</span><span class="p">;</span>
            <span class="mi">8</span>
        <span class="p">}</span>
    <span class="p">}</span> <span class="n">st</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">vis</span><span class="p">[</span><span class="n">maxs</span><span class="p">];</span>
    <span class="n">priority_queue</span><span class="o">&lt;</span><span class="n">Node</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span>
    <span class="kr">inline</span> <span class="kt">int</span> <span class="nf">cantor</span><span class="p">(</span><span class="n">string</span> <span class="n">s</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">memset</span><span class="p">(</span><span class="n">bit</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">bit</span><span class="p">));</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;x&#39;</span><span class="p">)</span>
                <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="sc">&#39;0&#39;</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">8</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">i</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">ans</span> <span class="o">+=</span> <span class="n">ask</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;0&#39;</span><span class="p">)</span> <span class="o">*</span> <span class="n">fact</span><span class="p">[</span><span class="mi">8</span> <span class="o">-</span> <span class="n">i</span><span class="p">];</span>
            <span class="n">add</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;0&#39;</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kr">inline</span> <span class="kt">int</span> <span class="nf">diff</span><span class="p">(</span><span class="n">string</span> <span class="n">s</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">i</span> <span class="o">/</span> <span class="mi">3</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">i</span> <span class="o">%</span> <span class="mi">3</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;x&#39;</span><span class="p">)</span>
                <span class="n">ans</span> <span class="o">+=</span> <span class="n">abs</span><span class="p">(</span><span class="n">x</span> <span class="o">-</span> <span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">abs</span><span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="mi">2</span><span class="p">);</span>
            <span class="k">else</span>
            <span class="p">{</span>
                <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;1&#39;</span><span class="p">;</span>
                <span class="n">ans</span> <span class="o">+=</span> <span class="n">abs</span><span class="p">(</span><span class="n">x</span> <span class="o">-</span> <span class="n">j</span> <span class="o">/</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="n">abs</span><span class="p">(</span><span class="n">y</span> <span class="o">-</span> <span class="n">j</span> <span class="o">%</span> <span class="mi">3</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kr">inline</span> <span class="n">string</span> <span class="nf">bfs</span><span class="p">(</span><span class="n">string</span> <span class="n">s</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;x&#39;</span><span class="p">)</span>
                <span class="n">st</span><span class="p">.</span><span class="n">i</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
        <span class="n">st</span><span class="p">.</span><span class="n">x</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">st</span><span class="p">.</span><span class="n">y</span> <span class="o">=</span> <span class="n">diff</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
        <span class="n">st</span><span class="p">.</span><span class="n">s</span> <span class="o">=</span> <span class="n">s</span><span class="p">,</span> <span class="n">st</span><span class="p">.</span><span class="n">ans</span> <span class="o">=</span> <span class="s">&quot;&quot;</span><span class="p">;</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">cantor</span><span class="p">(</span><span class="n">st</span><span class="p">.</span><span class="n">s</span><span class="p">)]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="mi">9</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">st</span><span class="p">);</span>
        <span class="k">while</span> <span class="p">(</span><span class="o">!</span><span class="n">q</span><span class="p">.</span><span class="n">empty</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">Node</span> <span class="n">u</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">top</span><span class="p">(),</span> <span class="n">v</span><span class="p">;</span>
            <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">u</span><span class="p">.</span><span class="n">s</span> <span class="o">==</span> <span class="s">&quot;12345678x&quot;</span><span class="p">)</span>
                <span class="k">return</span> <span class="n">u</span><span class="p">.</span><span class="n">ans</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">u</span><span class="p">.</span><span class="n">i</span> <span class="o">/</span> <span class="mi">3</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">u</span><span class="p">.</span><span class="n">i</span> <span class="o">%</span> <span class="mi">3</span><span class="p">;</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">4</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="kt">int</span> <span class="n">nx</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="n">nxt</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">ny</span> <span class="o">=</span> <span class="n">y</span> <span class="o">+</span> <span class="n">nxt</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">nx</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">nx</span> <span class="o">&gt;</span> <span class="mi">2</span> <span class="o">||</span> <span class="n">ny</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">ny</span> <span class="o">&gt;</span> <span class="mi">2</span><span class="p">)</span>
                    <span class="k">continue</span><span class="p">;</span>
                <span class="n">v</span><span class="p">.</span><span class="n">i</span> <span class="o">=</span> <span class="mi">3</span> <span class="o">*</span> <span class="n">nx</span> <span class="o">+</span> <span class="n">ny</span><span class="p">;</span>
                <span class="n">v</span><span class="p">.</span><span class="n">s</span> <span class="o">=</span> <span class="n">u</span><span class="p">.</span><span class="n">s</span><span class="p">;</span>
                <span class="n">swap</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">s</span><span class="p">[</span><span class="n">u</span><span class="p">.</span><span class="n">i</span><span class="p">],</span> <span class="n">v</span><span class="p">.</span><span class="n">s</span><span class="p">[</span><span class="n">v</span><span class="p">.</span><span class="n">i</span><span class="p">]);</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">cantor</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">s</span><span class="p">)])</span>
                    <span class="k">continue</span><span class="p">;</span>
                <span class="n">vis</span><span class="p">[</span><span class="n">cantor</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">s</span><span class="p">)]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
                <span class="n">v</span><span class="p">.</span><span class="n">x</span> <span class="o">=</span> <span class="n">u</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">v</span><span class="p">.</span><span class="n">y</span> <span class="o">=</span> <span class="n">diff</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">s</span><span class="p">);</span>
                <span class="n">v</span><span class="p">.</span><span class="n">ans</span> <span class="o">=</span> <span class="n">u</span><span class="p">.</span><span class="n">ans</span> <span class="o">+</span> <span class="n">dir</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
                <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">v</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="s">&quot;unsolvable&quot;</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span> <span class="n">a_star</span><span class="p">;</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="kt">char</span> <span class="n">in</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span>
    <span class="n">string</span> <span class="n">s</span> <span class="o">=</span> <span class="s">&quot;&quot;</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="mi">9</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%s&quot;</span><span class="p">,</span> <span class="n">in</span><span class="p">);</span>
        <span class="n">s</span> <span class="o">+=</span> <span class="n">in</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">8</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">i</span><span class="p">)</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="sc">&#39;x&#39;</span><span class="p">)</span>
            <span class="n">cnt</span> <span class="o">+=</span> <span class="n">a_star</span><span class="p">.</span><span class="n">ask</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;0&#39;</span><span class="p">),</span> <span class="n">a_star</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;0&#39;</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">cnt</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;unsolvable&quot;</span><span class="p">);</span>
    <span class="k">else</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">a_star</span><span class="p">.</span><span class="n">bfs</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="c1">// IDA* 解决八数码问题</span>
<span class="cp">#include</span> <span class="cpf">&lt;stdio.h&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;math.h&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;string.h&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="cp">#define INF 40000</span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">f</span><span class="p">[</span><span class="mi">10</span><span class="p">];</span>
<span class="k">class</span> <span class="nc">IDAStar</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">dx</span><span class="p">[</span><span class="mi">10</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">};</span>
    <span class="kt">int</span> <span class="n">dy</span><span class="p">[</span><span class="mi">10</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">};</span>
    <span class="kt">char</span> <span class="n">dxy</span><span class="p">[</span><span class="mi">10</span><span class="p">]</span> <span class="o">=</span> <span class="s">&quot;rldu&quot;</span><span class="p">;</span>
    <span class="kt">char</span> <span class="n">ans</span><span class="p">[</span><span class="mi">1005</span><span class="p">];</span>
    <span class="kt">int</span> <span class="nf">hh</span><span class="p">()</span> <span class="c1">//估值函数=每一个都直接走到自己位置的步数</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
                <span class="n">sum</span> <span class="o">+=</span> <span class="n">abs</span><span class="p">(</span><span class="n">i</span> <span class="o">/</span> <span class="mi">3</span> <span class="o">-</span> <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="n">abs</span><span class="p">(</span><span class="n">i</span> <span class="o">%</span> <span class="mi">3</span> <span class="o">-</span> <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="mi">3</span><span class="p">);</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">sum</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="n">minn</span><span class="p">;</span>
    <span class="kt">bool</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">g</span><span class="p">,</span> <span class="kt">int</span> <span class="n">depth</span><span class="p">)</span> <span class="c1">//x 代表&#39;x&#39;的位置 g 代表现在走了多少 depth 代表本次最</span>
        <span class="err">多走多少</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">h</span> <span class="o">=</span> <span class="n">hh</span><span class="p">();</span>
        <span class="n">minn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">minn</span><span class="p">,</span> <span class="n">h</span><span class="p">);</span> <span class="c1">//找到这次离终点最近的距离是多少，但实际距离一定是&gt;=估计</span>
        <span class="err">距离</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">h</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">ans</span><span class="p">[</span><span class="n">g</span><span class="p">]</span> <span class="o">=</span> <span class="sc">&#39;\0&#39;</span><span class="p">;</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%s</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">ans</span><span class="p">);</span>
            <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">g</span> <span class="o">+</span> <span class="n">h</span> <span class="o">&gt;</span> <span class="n">depth</span><span class="p">)</span>
            <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">xx</span><span class="p">,</span> <span class="n">yy</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">4</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">xx</span> <span class="o">=</span> <span class="n">x</span> <span class="o">/</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">dx</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="mi">11</span> <span class="n">yy</span> <span class="o">=</span> <span class="n">x</span> <span class="o">%</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">dy</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">xx</span> <span class="o">&gt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">yy</span> <span class="o">&gt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">xx</span> <span class="o">&lt;</span> <span class="mi">3</span> <span class="o">&amp;&amp;</span> <span class="n">yy</span> <span class="o">&lt;</span> <span class="mi">3</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">g</span><span class="p">)</span>
                <span class="p">{</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">ans</span><span class="p">[</span><span class="n">g</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;l&#39;</span><span class="p">)</span>
                        <span class="k">continue</span><span class="p">;</span> <span class="c1">//这次往上，上次往下肯定是不可以的</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">ans</span><span class="p">[</span><span class="n">g</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;r&#39;</span><span class="p">)</span>
                        <span class="k">continue</span><span class="p">;</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="mi">2</span> <span class="o">&amp;&amp;</span> <span class="n">ans</span><span class="p">[</span><span class="n">g</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;u&#39;</span><span class="p">)</span>
                        <span class="k">continue</span><span class="p">;</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="mi">3</span> <span class="o">&amp;&amp;</span> <span class="n">ans</span><span class="p">[</span><span class="n">g</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;d&#39;</span><span class="p">)</span>
                        <span class="k">continue</span><span class="p">;</span>
                <span class="p">}</span>
                <span class="n">ans</span><span class="p">[</span><span class="n">g</span><span class="p">]</span> <span class="o">=</span> <span class="n">dxy</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
                <span class="n">f</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">f</span><span class="p">[</span><span class="n">xx</span> <span class="o">*</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">yy</span><span class="p">];</span>
                <span class="n">f</span><span class="p">[</span><span class="n">xx</span> <span class="o">*</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">yy</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">dfs</span><span class="p">(</span><span class="n">xx</span> <span class="o">*</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">yy</span><span class="p">,</span> <span class="n">g</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">depth</span><span class="p">))</span>
                    <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
                <span class="n">f</span><span class="p">[</span><span class="n">xx</span> <span class="o">*</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">yy</span><span class="p">]</span> <span class="o">=</span> <span class="n">f</span><span class="p">[</span><span class="n">x</span><span class="p">];</span>
                <span class="n">f</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">IDA_star</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">depth</span> <span class="o">=</span> <span class="n">hh</span><span class="p">();</span>
        <span class="k">while</span> <span class="p">(</span><span class="mi">1</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">minn</span> <span class="o">=</span> <span class="n">INF</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">dfs</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">depth</span><span class="p">))</span>
            <span class="p">{</span>
                <span class="k">break</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">depth</span> <span class="o">+=</span> <span class="n">minn</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">bool</span> <span class="nf">pan</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">9</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="k">for</span> <span class="p">(</span><span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span>
                <span class="mi">12</span>
                <span class="p">{</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
                        <span class="n">k</span><span class="o">++</span><span class="p">;</span>
                <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">k</span> <span class="o">%</span> <span class="mi">2</span><span class="p">)</span>
            <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span> <span class="n">ida_star</span><span class="p">;</span>
<span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">105</span><span class="p">];</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">gets</span><span class="p">(</span><span class="n">a</span><span class="p">))</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">a1</span> <span class="o">=</span> <span class="n">strlen</span><span class="p">(</span><span class="n">a</span><span class="p">),</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">a1</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="sc">&#39; &#39;</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">&#39;x&#39;</span><span class="p">)</span>
                <span class="p">{</span>
                    <span class="n">x</span> <span class="o">=</span> <span class="n">k</span> <span class="o">/</span> <span class="mi">3</span><span class="p">;</span>
                    <span class="n">y</span> <span class="o">=</span> <span class="n">k</span> <span class="o">%</span> <span class="mi">3</span><span class="p">;</span>
                    <span class="n">f</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
                    <span class="n">k</span><span class="o">++</span><span class="p">;</span>
                <span class="p">}</span>
                <span class="k">else</span>
                    <span class="n">f</span><span class="p">[</span><span class="n">k</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="sc">&#39;0&#39;</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">ida_star</span><span class="p">.</span><span class="n">pan</span><span class="p">())</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&quot;unsolvable</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
        <span class="k">else</span>
            <span class="n">ida_star</span><span class="p">.</span><span class="n">IDA_star</span><span class="p">(</span><span class="n">x</span> <span class="o">*</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">y</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>
<span class="c1">// 1 2 3 4 5 6 7 8 x</span>
</code></pre></div>
</td></tr></table>

<div class="admonition check">
<p class="admonition-title">整理人</p>
<p>计 16-1 刘明辉</p>
</div>
                
                  
                
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid">
        
          <a href="../%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alpha-beta%E5%89%AA%E6%9E%9D/" title="极大极小化搜索" class="md-flex md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-back md-footer-nav__button"></i>
            </div>
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  上一页
                </span>
                极大极小化搜索
              </span>
            </div>
          </a>
        
        
          <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" title="状态压缩DP" class="md-flex md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  下一页
                </span>
                状态压缩DP
              </span>
            </div>
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-forward md-footer-nav__button"></i>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
        powered by
        <a href="https://www.mkdocs.org" target="_blank" rel="noopener">MkDocs</a>
        and
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs</a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/application.c33a9706.js"></script>
      
        
        
          
          <script src="../../assets/javascripts/lunr/lunr.stemmer.support.js"></script>
          
            
              
                <script src="../../assets/javascripts/lunr/tinyseg.js"></script>
              
              
                <script src="../../assets/javascripts/lunr/lunr.ja.js"></script>
              
            
          
          
        
      
      <script>app.initialize({version:"1.1",url:{base:"../.."}})</script>
      
        <script src="https://cdnjs.loli.net/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>